package com.suanfa;


/**
 * 分块查找法
 *
 * @Author weijingchen
 * @Date 2025/5/28 20:22
 * @Version 1.0.0
 */
public class Test08 {
    public static void main(String[] args) {
        /*
            分块查找
            核心思想
                块内无需，块间有序
             实现步骤
                1.创建数组blockArr存放每一个快对象
                2.先查找blockArr 确定要查找的数据属于那一块
                3.再单独遍历这一块的数据
         */
        int[] arr = {16, 5, 9, 12, 21, 18, 32, 23, 37, 26, 45, 34, 50, 48, 61, 52, 73, 66};

        //创建三个块对象
        Block b1 = new Block(21, 0, 5);
        Block b2 = new Block(45, 6, 11);
        Block b3 = new Block(75, 12, 17);

        //定义一个数组用来管理这三个块对象
        Block[] blockArr = {b1, b2, b3};

        //定义一个变量用来记录要查找的数
        int num = 52;
        //调用方法，传递索引表，数组，要查找的元素
        int index = getIndex(blockArr, arr, num);
        System.out.println("num:" + num + "在数组中的索引是：" + index);
    }

    private static int getIndex(Block[] blockArr, int[] arr, int num) {

        int indexBlock = getBlock(blockArr, num);
        if (indexBlock == -1) {
            //表示数组中没有这个数
            return -1;
        }
        int startIndex = blockArr[indexBlock].getStartIndex();
        int endIndex = blockArr[indexBlock].getEndIndex();
        for (int i = startIndex; i <= endIndex; i++) {
            if (arr[i] == num) {
                return i;
            }
        }

        return 0;
    }

    //定义一个方法，用来确定number在那一块
    public static int getBlock(Block[] blockArr, int num) {

        for (int i = 0; i < blockArr.length; i++) {
            if (num <= blockArr[i].getMax()) {
                return i;
            }
        }
        return -1;
    }

}

class Block {
    private int max;
    private int startIndex;
    private int endIndex;


    public Block() {
    }

    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    /**
     * 获取
     *
     * @return max
     */
    public int getMax() {
        return max;
    }

    /**
     * 设置
     *
     * @param max
     */
    public void setMax(int max) {
        this.max = max;
    }

    /**
     * 获取
     *
     * @return startIndex
     */
    public int getStartIndex() {
        return startIndex;
    }

    /**
     * 设置
     *
     * @param startIndex
     */
    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    /**
     * 获取
     *
     * @return endIndex
     */
    public int getEndIndex() {
        return endIndex;
    }

    /**
     * 设置
     *
     * @param endIndex
     */
    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public String toString() {
        return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
}